Corner detection

 ( Feature Detection ) 

Without loss of generality, we will assume a grayscale 2-dimensional image is used. Let this image be given by $I$. Consider taking an image patch over the area $(u,\; v)$ and shifting it by $(x,\; y)$. The weighted sum of squared differences (SSD) between these two patches, denoted $S$, is given by $$$$

S(x, y) = \sum_u \sum_v w(u, v) [I(u + x, v + y) - I(u, v)]^2.
     

I(u + x, v + y) \approx I(u, v) + I_x(u, v) x + I_y(u, v) y.
     

This produces the approximation $$$$

S(x, y) \approx \sum_u \sum_v w(u, v) [I_x(u, v) x + I_y(u, v) y]^2,
     

S(x, y) \approx \begin{bmatrix} x & y \end{bmatrix} A \begin{bmatrix} x \\ y \end{bmatrix},
     

A = \sum_u \sum_v w(u, v) \begin{bmatrix}
 I_x(u, v)^2        & I_x(u, v) I_y(u, v) \\
 I_x(u, v) I_y(u,v) & I_y(u, v)^2
\end{bmatrix} = \begin{bmatrix}
 \langle I_x^2 \rangle   & \langle I_x I_y \rangle \\
 \langle I_x I_y \rangle & \langle I_y^2 \rangle
\end{bmatrix}.
     

In words, we find the covariance of the partial derivative of the image intensity $I$ with respect to the $x$ and $y$ axes.

Angle brackets denote averaging (i.e. summation over $(u,\; v)$), and $w(u,\; v)$ denotes the type of window that slides over the image. If a Box blur is used, the response will be Anisotropy, but if a Gaussian is used, then the response will be isotropic.

A corner (or in general an interest point) is characterized by a large variation of $S$ in all directions of the vector . By analyzing the eigenvalues of $A$, this characterization can be expressed in the following way: $A$ should have two "large" eigenvalues for an interest point. Based on the magnitudes of the eigenvalues, the following inferences can be made based on this argument:

1. If $\backslash lambda\_1\; \backslash approx\; 0$ and $\backslash lambda\_2\; \backslash approx\; 0,$ then this pixel $(x,\; y)$ has no features of interest.
2. If $\backslash lambda\_1\; \backslash approx\; 0$ and $\backslash lambda\_2$ has some large positive value, then an edge is found.
3. If $\backslash lambda\_1$ and $\backslash lambda\_2$ have large positive values, then a corner is found.

Harris and Stephens note that exact computation of the eigenvalues is computationally expensive, since it requires the computation of a square root, and instead suggest the function $$$$

M_c = \lambda_1 \lambda_2 - \kappa (\lambda_1 + \lambda_2)^2
= \det(A) - \kappa \operatorname{tr}^2(A),
     

Therefore, the algorithm does not have to actually compute the eigenvalue decomposition of the matrix $A,$ and instead it is sufficient to evaluate the determinant and trace of $A$ to find corners, or rather interest points in general.

The Shi–Tomasi corner detector directly computes $\backslash min(\backslash lambda\_1,\; \backslash lambda\_2)$ because under certain assumptions, the corners are more stable for tracking. Note that this method is also sometimes referred to as the Kanade–Tomasi corner detector.

The value of $\backslash kappa$ has to be determined empirically, and in the literature values in the range 0.04–0.15 have been reported as feasible.

One can avoid setting the parameter $\backslash kappa$ by using Noble's corner measure $M\_c\text{'}$ which amounts to the harmonic mean of the eigenvalues: $$$$

M_c' = 2 \frac{\det(A)}{\operatorname{tr}(A) + \epsilon},
     

If $A$ can be interpreted as the precision matrix for the corner position, the covariance matrix for the corner position is $A^\{-1\}$, i.e. $$$$

\frac{1}{\langle I_x^2 \rangle \langle I_y^2 \rangle - \langle I_x I_y \rangle^2} \begin{bmatrix}
 \langle I_y^2 \rangle    & -\langle I_x I_y \rangle \\
 -\langle I_x I_y \rangle & \langle I_x^2 \rangle
\end{bmatrix}.
     

The sum of the eigenvalues of $A^\{-1\}$, which in that case can be interpreted as a generalized variance (or a "total uncertainty") of the corner position, is related to Noble's corner measure $M\_c\text{'}$ as $$$$

\lambda_1(A^{-1}) + \lambda_2(A^{-1}) = \frac{\operatorname{tr}(A)}{\det(A)} \approx \frac{2}{M_c'}.
     

The equation of a tangent line $T\_\{\backslash mathbf\{x\}\text{'}\}(\backslash mathbf\{x\})$ at pixel $\backslash mathbf\{x\}\text{'}$ is given by:

$T\_\backslash mathbf\{x\text{'}\}(\backslash mathbf\; x)\; =\; \backslash nabla\; I(\backslash mathbf\{x\text{'}\})^\{\backslash top\}(\backslash mathbf\{x\}-\backslash mathbf\{x\text{'}\})\; =\; 0$

where is the gradient vector of the image $I$ at $\backslash mathbf\{x\text{'}\}$.

The point $\backslash mathbf\{x\}\_\{0\}$ closest to all the tangent lines in the window $N$ is:

$\backslash mathbf\{x\}\_\{0\}=\backslash underset\{\backslash mathbf\{x\}\backslash in\; \backslash mathbb\{R\}^\{2\backslash times\; 1\}\}\{\backslash operatorname\{argmin\}\}\backslash int\_\{\backslash mathbf\{x\text{'}\}\backslash in\; N\}T\_\{\backslash mathbf\{x\text{'}\}\}(\backslash mathbf\{x\})^\{2\}d\backslash mathbf\{x\text{'}\}$

The distance from $\backslash mathbf\{x\}\_\{0\}$ to the tangent lines $T\_\{\backslash mathbf\{x\text{'}\}\}$ is weighted by the gradient magnitude, thus giving more importance to tangents passing through pixels with strong gradients.

Solving for $\backslash mathbf\{x\}\_\{0\}$:

$A\backslash in\backslash mathbb\{R\}^\{2\backslash times\; 2\},\backslash textbf\{b\}\backslash in\backslash mathbb\{R\}^\{2\backslash times\; 1\},c\backslash in\backslash mathbb\{R\}$ are defined as:

Minimizing this equation can be done by differentiating with respect to $x$ and setting it equal to 0:

$2A\backslash mathbf\{x\}-2\backslash mathbf\{b\}=0\; \backslash Rightarrow\; A\backslash mathbf\{x\}=\backslash mathbf\{b\}$

Note that $A\backslash in\backslash mathbb\{R\}^\{2\backslash times\; 2\}$ is the structure tensor. For the equation to have a solution, $A$ must be invertible, which implies that $A$ must be full rank (rank 2). Thus, the solution

$x\_\{0\}=A^\{-1\}\backslash mathbf\{b\}$

only exists where an actual corner exists in the window $N$.

A methodology for performing automatic scale selection for this corner localization method has been presented by Lindeberg by minimizing the normalized residual

$\backslash tilde\{d\}\_\{\backslash min\}\; =\; \backslash frac\{c\; -\; b^T\; A^\{-1\}\; b\}\{\backslash operatorname\{trace\}\; A\}$

over scales. Thereby, the method has the ability to automatically adapt the scale levels for computing the image gradients to the noise level in the image data, by choosing coarser scale levels for noisy image data and finer scale levels for near ideal corner-like structures.

Notes:

• $c$ can be viewed as a residual in the least-square solution computation: if $c=0$, then there was no error.
• this algorithm can be modified to compute centers of circular features by changing tangent lines to normal lines.

With $I$ denoting the original image intensity, let $L$ denote the scale space representation of $I$ obtained by convolution with a Gaussian kernel

$g(x,\; y,\; t)\; =\; \backslash frac\; \{1\}\{2\{\backslash pi\}\; t\}\; e^\{-\backslash left(x^2+y^2\backslash right)/2t\}$

$L(x,\; y,\; t)\backslash \; =\; g(x,\; y,\; t)\; *\; I(x,\; y)$

   \begin{cases}
     t^2 \, (\det H L - k \, \operatorname{trace}^2 H L)
       & \mbox{if} \, \det H L - k \, \operatorname{trace}^2 H L > 0 \\
     0 & \mbox{otherwise}
   \end{cases}
     

   \begin{cases}
     t^2 \, (\det H L - k \, \operatorname{trace}^2 H L)
       & \mbox{if} \, \det H L - k \, \operatorname{trace}^2 H L > 0 \\
    t^2 \, (\det H L + k \, \operatorname{trace}^2 H L)
       & \mbox{if} \, \det H L + k \, \operatorname{trace}^2 H L < 0 \\
     0 & \mbox{otherwise}
   \end{cases}
     

   \begin{cases}
     t \, \lambda_1(H L)
       & \mbox{if} \, |\lambda_1(H L)| < |\lambda_2(H L)| \\
    t \, \lambda_2(H L)
       & \mbox{if} \, |\lambda_2(H L)| < |\lambda_1(H L)| \\
     t \, (\lambda_1(H L) + \lambda_2(H L))/2 & \mbox{otherwise}
   \end{cases}
     

              g - n(M) & \mbox{if}\ n(M) < g\\
              0        & \mbox{otherwise,}
          \end{cases}
     

r(\vec{c}) = \min_{\vec{p} \in P} \left(\left(I(\vec{p}) - I(\vec{c})\right)^2 + \left(I(\vec{p}') - I(\vec{c})\right) ^2\right)
     

   = \, s^{2 \gamma_s} \tau^{\gamma_{\tau}}
       \left( L_{xx} L_{yy} L_{tt} + 2 L_{xy} L_{xt} L_{yt}
      - L_{xx} L_{yt}^2 - L_{yy} L_{xt}^2 - L_{tt} L_{xy}^2 \right).